TNotes.leetcode

Appearance

0017. 电话号码的字母组合【中等】

0017. 电话号码的字母组合【中等】 ​

1. 📝 题目描述 ​

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

img

示例 1：

txt
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

txt
输入：digits = ""
输出：[]

示例 3：

txt
输入：digits = "2"
输出：["a","b","c"]

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

2. 🎯 s.1 - 回溯 ​

c
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
const char* MAP[] = {"",    "",    "abc",  "def", "ghi",
                     "jkl", "mno", "pqrs", "tuv", "wxyz"};

void backtrack(char* digits, int index, char* path, int pathLen, char** ans,
               int* returnSize) {
    if (digits[index] == '\0') {
        ans[*returnSize] = (char*)malloc((pathLen + 1) * sizeof(char));
        strncpy(ans[*returnSize], path, pathLen);
        ans[*returnSize][pathLen] = '\0';
        (*returnSize)++;
        return;
    }
    const char* letters = MAP[digits[index] - '0'];
    for (int i = 0; letters[i] != '\0'; i++) {
        path[pathLen] = letters[i];
        backtrack(digits, index + 1, path, pathLen + 1, ans, returnSize);
    }
}

char** letterCombinations(char* digits, int* returnSize) {
    *returnSize = 0;
    int n = strlen(digits);
    if (n == 0)
        return NULL;

    // 最多 4 个数字，每个最多 4 个字母，最多 4^4 = 256 种组合
    char** ans = (char**)malloc(256 * sizeof(char*));
    char* path = (char*)malloc((n + 1) * sizeof(char));
    backtrack(digits, 0, path, 0, ans, returnSize);
    free(path);
    return ans;
}
js
/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  if (!digits.length) return []

  const map = {
    2: 'abc',
    3: 'def',
    4: 'ghi',
    5: 'jkl',
    6: 'mno',
    7: 'pqrs',
    8: 'tuv',
    9: 'wxyz',
  }
  const ans = []

  const backtrack = (index, path) => {
    if (index === digits.length) {
      ans.push(path)
      return
    }
    for (const ch of map[digits[index]]) {
      backtrack(index + 1, path + ch)
    }
  }

  backtrack(0, '')
  return ans
}
py
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        phone_map = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        ans = []

        def backtrack(index: int, path: str) -> None:
            if index == len(digits):
                ans.append(path)
                return
            for ch in phone_map[digits[index]]:
                backtrack(index + 1, path + ch)

        backtrack(0, "")
        return ans
  • 时间复杂度：O(4n⋅n)，其中 n 是输入数字个数（最多为 4），4n 是最多的组合数，每个组合需 O(n) 构建
  • 空间复杂度：O(n)，递归栈深度最多为 n（不计输出数组）

算法思路：

  • 用哈希表建立数字到字母的映射
  • 回渥枚举：每层取当前数字对应的每一个字母，拼接到路径 path 后递归处理下一个数字
  • 当索引走到末尾（index == n）时，将当前路径加入结果集

Discussions